package 剑指专题.二叉树;


/*
 * Author：江松
 * Date：2023/3/25 15:42
 *
 二叉搜索树的最近公共祖先：
1,直接从根节点遍历到指定2点，然后对比2个序列，最后一个相同值就是公共祖先
2,一次遍历（分类递归),根在2值中间的话就返回，否则继续找对应左右子树
 */

import org.omg.CORBA.INTERNAL;

import java.util.ArrayList;

public class Main12 {
    class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    public int lowestCommonAncestor (TreeNode root, int p, int q) {
        if(root==null)return -1;
        if((p<=root.val&&q>=root.val)||(p>=root.val&&q<=root.val)){
            return root.val;
        }else if(p>root.val||q>root.val){
            return lowestCommonAncestor(root.right,p,q);
        }else{
            return lowestCommonAncestor(root.left,p,q);
        }
    }

    /*
    public ArrayList<Integer> findPath(TreeNode root,int val){
        ArrayList<Integer>path=new ArrayList<>();
        while(root!=null&&root.val!=val){
            path.add(root.val);
            if(val<root.val){
                root=root.left;
            }else if(val>root.val){
                root=root.right;
            }else{
                break;
            }
        }
        return path;
    }
    public int lowestCommonAncestor (TreeNode root, int p, int q) {
        ArrayList<Integer>ap=findPath(root,p);
        ArrayList<Integer>aq=findPath(root,q);
        System.out.println(aq);
        int ans=root.val;
        for(int i=0;i<Math.min(ap.size(),aq.size());++i){
            int vp=ap.get(i),vq=aq.get(i);
            System.out.println("vp:"+vp+",vq"+vq);
            if(vp==vq)ans=ap.get(i);
        }
        return ans;
    }
    */
}
